package day9;

import java.util.*;

public class code3 {


    public static int num = 0;
    public static int m = 0;
    public static int n = 0;
    public int kthSmallest(TreeNode root, int k) {
        n = 0;
        m = k;
        fun(root);

        return num;


    }

    public void fun(TreeNode node){
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (!stack.isEmpty()||node!=null){
            while (node!=null){
                stack.push(node);
                node = node.left;
            }
            n++;
            TreeNode tep = stack.pop();
            if(n==m){
                num = tep.val;
                return;
            }
            node = tep.right;

        }

    }

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if(root==null) return list;
        queue.offer(root);
        while (!queue.isEmpty()){
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode tep = queue.poll();
                if(i==len-1) list.add(tep.val);
                if(tep.left!=null) queue.offer(tep.left);
                if(tep.right!=null) queue.offer(tep.right);
            }
        }

        return list;


    }

    public void flatten(TreeNode root) {
        TreeNode node  = root;
        while (node!=null){
            if(node.left!=null){
                TreeNode lt = node.left;
                while (lt.right!=null){
                    lt = lt.right;
                }
                lt.right = node.right;
                node.right = node.left;
                node.left = null;
            }
            node = node.right;

        }

    }



    public static int[] pr;
    public static int[] in;
    public static HashMap<Integer,Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        pr = preorder;
        in = inorder;

        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        TreeNode root = new TreeNode(preorder[0]);
        fun(0,preorder.length-1,root,0);

        return root;
    }

    public void fun(int lt,int rt,TreeNode node,int index){
        if(lt>=rt) return;

        int num = map.get(node.val);

        int k1 = num-lt;
        int k2 = rt-num;

        if(k1>0){
            TreeNode l = new TreeNode(pr[index+1]);
            node.left = l;
            fun(lt,num-1,l,index+1);
        }
        if(k2>0){
            TreeNode r = new TreeNode(pr[index+k1+1]);
            node.right = r;
            fun(num+1,rt,r,index+k1+1);

        }


    }





}
